package lru;

import java.util.HashMap;
import java.util.LinkedList;

class Entity {
    String key;
    int val;
    public Entity(String key, int val) {
        this.key = key;
        this.val = val;
    }
    public Entity() {

    }
    Entity pre;
    Entity next;
}

// 实现 LRU 算法
public class LRU {
    // 缓存容量
    int capacity;
    // 使用容量
    int size;
    // 缓存链表
    Entity head;
    Entity tail;
    // 加速访问的map
    HashMap<String, Entity> cache;

    /**
     * 初始化
     */
    public LRU(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        head = new Entity();
        tail = new Entity();

        head.next = tail;
        tail.pre = head;
        cache = new HashMap<>();
    }

    /**
     * 取缓存
     */
    public int getCache(String key) {
        Entity entity = cache.get(key);
        // 缓存不存在
        if (entity == null) {
            return -1;
        }
        // 缓存存在, 将当前entity挪到最前面返回
        moveToHead(entity);
        return entity.val;
    }

    private void moveToHead(Entity entity) {
        // 1.修改当前指针指向（删除原来entity）
        entity.pre.next = entity.next;
        entity.next.pre = entity.pre;
        // 2.放到队首
        Entity node = head.next;
        head.next = entity;
        entity.pre = head;
        entity.next = node;
        node.pre = entity;
    }

    /**
     * 添加缓存
     */
    public void setCache(String key, int val) {
        Entity entity = cache.get(key);
        // 缓存存在
        if (entity != null) {
            // 修改缓存val
            entity.val = val;
            // 放到队首
            moveToHead(entity);
            return;
        }
        // 缓存不存在
        // 先判断容量
        if (size == capacity) {
            System.out.println(size);
            // 容量已满，删除队尾元素
            delLast();
            size--;
        }
        // 添加到头结点
        Entity newNode = new Entity(key, val);
        Entity tmp = head.next;
        head.next = newNode;
        newNode.pre = head;
        newNode.next = tmp;
        tmp.pre = newNode;
        cache.put(key, newNode);
        size++;
    }

    private void delLast() {
        cache.remove(tail.pre.key);
        tail.pre.pre.next = tail;
        tail.pre = tail.pre.pre;
    }

    public static void main(String[] args) {
        LRU lru = new LRU(2);
        lru.setCache("1",1);
        lru.setCache("2",2);
        System.out.println(lru.getCache("1"));
        lru.setCache("3",3);
        System.out.println(lru.getCache("2"));
        System.out.println(lru.getCache("3"));
    }
}
